package ljl.alg.wangzheng_camp.round1.find_the_law;

/**
 * 我一看，就知道是个好题
 * 不过怎么做呢...
 * */
public class _55_can_jump {
    
    /*
    * 2,3,1,1,4
    *
    * 我想来个回溯之类的，不过这个题没归类到回溯上，会不会不是回溯？
    *
    * 我思路，找个数组标记那个数字走过了
    * 然后没走过的，挨个试，如果走到最后返回 true，都走过了，返回 false
    * */
    /**
     * 卧槽居然过了
     * 虽然效率非常的低
     *
     * 我牛逼！
     *
     * */
    public boolean canJump2(int[] nums) {
        return jump(nums, new boolean[nums.length], 0);
    }
    // 当前在 pos 这个位置，可以拿到 pos 这的长度，然后遍历
    boolean jump(int[] nums, boolean[] visited, int pos) {
        if (pos == nums.length - 1) return true;
        if (visited[pos]) return false;
        visited[pos] = true;
        int len = nums[pos];
        // 都跳不过去返回 false
        for (int i = 1; i <= len; i++) {
            if (jump(nums, visited, pos + i))
                return true;
        }
        return false;
    }
    
    /**
     * 官方用的贪心
     *
     * 每到一个可达的位置，更新最大可达位置，如果最大可达位置比最后大，直接返回 true
     * 继续去下一个位置，看是否在最大可达位置内；如果在，重复第一步
     *
     * 按说这么几行也不至于是中等
     * 不过也不至于是简单
     *
     * */
    public boolean canJump(int[] nums) {
        int father = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > father) return false;
            // 脑血栓多加了个 + 1
            father = Math.max(father, nums[i] + i);
            if (father >= nums.length - 1) return true;
        }
        return false;
    }
}
